package leetcode;

/**
 * @param
 * @author oyz
 * @version 1.0
 * @description: 给你一个字符串 s，找到 s 中最长的回文子串。
 * @date 2022/3/8 21:17
 */
public class Code5 {

    public static void main(String[] args) {
        System.out.println(new Code5().longestPalindrome("ac"));
    }

    public String longestPalindrome(String s) {
        int length = s.length();
        if (length <2){
            return s;
        }
        // 定义起始位置
        int begin = 0;
        // 定义最大长度
        int maxLength = 1;
        boolean dp[][] = new boolean[length][length];
        for (int i=0;i<length;i++){
            dp[i][i] = true;
        }
        char[] chars = s.toCharArray();
        // 按照一列一列的去填表
        for (int j=1;j<length;j++){
            for(int i=0;i<j;i++){
                if(chars[i] != chars[j]){
                    dp[i][j] = false;
                }else{
                    if(j-i<3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]&& j-i+1>maxLength){
                    begin = i;
                    maxLength = j-i+1;
                }
            }
        }
        return s.substring(begin,begin+maxLength);
    }
}
